{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Connect Sticks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: connectSticks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接棒材的最低费用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一些长度为正整数的棍子。这些长度以数组<meta charset=\"UTF-8\" />&nbsp;<code>sticks</code>&nbsp;的形式给出，<meta charset=\"UTF-8\" />&nbsp;<code>sticks[i]</code>&nbsp;是 <code>第i个</code> 木棍的长度。</p>\n",
    "\n",
    "<p>你可以通过支付 <code>x + y</code> 的成本将任意两个长度为 <code>x</code> 和 <code>y</code> 的棍子连接成一个棍子。你必须连接所有的棍子，直到剩下一个棍子。</p>\n",
    "\n",
    "<p>返回以这种方式将所有给定的棍子连接成一个棍子的 <em>最小成本</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sticks = [2,4,3]\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>从 sticks = [2,4,3] 开始。\n",
    "1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4]\n",
    "2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9]\n",
    "所有木棍已经连成一根，总费用 5 + 9 = 14\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sticks = [1,8,3,5]\n",
    "<strong>输出：</strong>30\n",
    "<strong>解释：</strong>从 sticks = [1,8,3,5] 开始。\n",
    "1. 连接 1 和 3 ，费用为 1 + 3 = 4 。现在 sticks = [4,8,5]\n",
    "2. 连接 4 和 5 ，费用为 4 + 5 = 9 。现在 sticks = [9,8]\n",
    "3. 连接 9 和 8 ，费用为 9 + 8 = 17 。现在 sticks = [17]\n",
    "所有木棍已经连成一根，总费用 4 + 9 + 17 = 30\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sticks = [5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>只有一根木棍，不必再连接。总费用 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= sticks.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= sticks[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-connect-sticks](https://leetcode.cn/problems/minimum-cost-to-connect-sticks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-connect-sticks](https://leetcode.cn/problems/minimum-cost-to-connect-sticks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,3]', '[1,8,3,5]', '[5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(sticks)\n",
    "        ans = 0\n",
    "        while len(sticks) > 1:\n",
    "            x, y = heapq.heappop(sticks), heapq.heappop(sticks)\n",
    "            ans += x + y\n",
    "            heapq.heappush(sticks, x + y)\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        h = sticks\n",
    "        heapify(h) \n",
    "        ans = 0\n",
    "        while len(h) >= 2:\n",
    "            s1, s2 = heappop(h), heappop(h)\n",
    "            ans += s1 + s2\n",
    "            heappush(h, s1 + s2)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        from heapq import heapify, heappush, heappop\n",
    "        heapify(sticks)\n",
    "        res = 0\n",
    "        while (len(sticks) > 1):\n",
    "            cand1 = heappop(sticks)\n",
    "            cand2 = heappop(sticks)\n",
    "            cand1 += cand2\n",
    "            res += cand1\n",
    "            heappush(sticks,cand1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        res = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            tmp = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            res += tmp \n",
    "            heapq.heappush(sticks, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, s: List[int]) -> int:\n",
    "        heapq.heapify(s)\n",
    "        ans = 0 \n",
    "        while len(s)>=2:\n",
    "            if len(s)==2:\n",
    "                return ans + sum(s) \n",
    "            else:\n",
    "                a = heapq.heappop(s)\n",
    "                b = heapq.heappop(s) \n",
    "                ans += a+b \n",
    "                heapq.heappush(s, a+b)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if not sticks:\n",
    "            return 0\n",
    "\n",
    "        from heapq import heapify, heappop, heappush\n",
    "        heapify(sticks)\n",
    "\n",
    "        cost = 0\n",
    "        while len(sticks) > 1:\n",
    "            stick1 = heappop(sticks)\n",
    "            stick2 = heappop(sticks)\n",
    "\n",
    "            new_stick = stick1 + stick2\n",
    "            cost += new_stick\n",
    "            heappush(sticks, new_stick)\n",
    "\n",
    "            # print(sticks)\n",
    "        \n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks) -> int:\n",
    "        \n",
    "        if len(sticks) <=1:\n",
    "            return 0\n",
    "        cost = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            x,y = heapq.heappop(sticks),heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks,(x+y))\n",
    "            cost += x+y\n",
    "        return cost \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        sticks.sort()\n",
    "        cost = 0\n",
    "        while len(sticks)>1:\n",
    "            a = heappop(sticks)\n",
    "            b = heappop(sticks)\n",
    "            cost += a+b\n",
    "            heappush(sticks, a+b)\n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)  # 将sticks转化为最小堆\n",
    "        cost = 0\n",
    "        \n",
    "        while len(sticks) > 1:\n",
    "            x = heapq.heappop(sticks)  # 取出最小的棍子\n",
    "            y = heapq.heappop(sticks)  # 再次取出最小的棍子\n",
    "            cost += x + y  # 这是当前步骤的成本\n",
    "            heapq.heappush(sticks, x + y)  # 将两根棍子连接后的长度放回堆中\n",
    "        \n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        n = len(sticks)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return sticks[0] + sticks[1]\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            t1 = heapq.heappop(sticks)\n",
    "            t2 = heapq.heappop(sticks)\n",
    "\n",
    "            ans += (t1 + t2)\n",
    "\n",
    "            heapq.heappush(sticks, t1 + t2)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        res = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            tmp = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            res += tmp\n",
    "            heapq.heappush(sticks, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def connectSticks(self, sticks):\n",
    "        \"\"\"\n",
    "        :type sticks: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from heapq import heapify, heappop, heappush\n",
    "        heapify(sticks) # 建优先级队列\n",
    "        res = 0\n",
    "        while len(sticks) > 1:\n",
    "            s1 = heappop(sticks) #找到最短的棒材\n",
    "            s2 = heappop(sticks) #找到第二短的棒材\n",
    "            res += s1 + s2 #把最短的两根棒子连接在一起\n",
    "            heappush(sticks, s1 + s2) #把连接好的棒材放进队\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heapify(sticks)\n",
    "        while len(sticks) >= 2:\n",
    "            a, b = heappop(sticks), heappop(sticks)\n",
    "            ans += a+b\n",
    "            heappush(sticks, a+b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heapq.heapify(sticks)\n",
    "\n",
    "        while len(sticks) > 1:\n",
    "            concat_stick = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            ans += concat_stick\n",
    "            heapq.heappush(sticks, concat_stick)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        heapq.heapify(sticks)\n",
    "        result = 0\n",
    "        while len(sticks) > 1:\n",
    "            left, right = heapq.heappop(sticks), heapq.heappop(sticks)\n",
    "            cur = left + right\n",
    "            result += cur\n",
    "            heapq.heappush(sticks, cur)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        cost=0\n",
    "        while len(sticks)>1:\n",
    "            x=heapq.heappop(sticks)\n",
    "            y=heapq.heappop(sticks)\n",
    "            cost+=x+y\n",
    "            heapq.heappush(sticks, x+y)\n",
    "\n",
    "        \n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapify(sticks)\n",
    "        ans = 0\n",
    "        while len(sticks) > 1:\n",
    "            cur = heappop(sticks) + heappop(sticks)\n",
    "            ans += cur\n",
    "            heappush(sticks, cur)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        res = 0\n",
    "        heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            tmp = heappop(sticks) + heappop(sticks)\n",
    "            res += tmp\n",
    "            heappush(sticks, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(sticks)\n",
    "        cost = 0\n",
    "        while len(sticks) > 1:\n",
    "            a = heapq.heappop(sticks)\n",
    "            b = heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks, a+b)\n",
    "            cost += a+b\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        cost = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            stick1 = heapq.heappop(sticks)\n",
    "            stick2 = heapq.heappop(sticks)\n",
    "            cost += stick1 + stick2\n",
    "            heapq.heappush(sticks, stick1+stick2)\n",
    "        return cost\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        cost = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            c = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks, c)\n",
    "            cost += c\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        \n",
    "        res = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            tmp = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            res += tmp\n",
    "            heapq.heappush(sticks, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        n = len(sticks)\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        heapq.heapify(sticks)\n",
    "        fee = 0\n",
    "        i = 0\n",
    "        while len(sticks) > 1:\n",
    "            tmp = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            fee += tmp\n",
    "            heapq.heappush(sticks, tmp)\n",
    "        return fee\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        res = 0\n",
    "        while(sticks):\n",
    "            if len(sticks)==1:\n",
    "                break\n",
    "            s1 = heapq.heappop(sticks)\n",
    "            s2 = heapq.heappop(sticks)\n",
    "            res += s1+s2\n",
    "            heapq.heappush(sticks, s1+s2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        ans = 0\n",
    "        while sticks:\n",
    "            if len(sticks) == 1: \n",
    "                return ans\n",
    "            \n",
    "            x = heapq.heappop(sticks)\n",
    "            y = heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks, x + y)\n",
    "            ans += x + y\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "\n",
    "        if len(sticks) < 2:\n",
    "            return 0\n",
    "        \n",
    "        print(sticks)\n",
    "        heapq.heapify(sticks)\n",
    "        cost = []\n",
    "        while len(sticks) > 2:\n",
    "            m,n = heapq.heappop(sticks),heapq.heappop(sticks)\n",
    "            s = m + n\n",
    "            cost.append(s)\n",
    "            heapq.heappush(sticks,s)\n",
    "\n",
    "        return sum(cost) + sum(sticks)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        n = len(sticks)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return sum(sticks)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            st1 = heapq.heappop(sticks)\n",
    "            st2 = heapq.heappop(sticks)\n",
    "            cost = st1 + st2\n",
    "\n",
    "            ans += cost\n",
    "            heapq.heappush(sticks, cost)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        result = 0\n",
    "        heapq.heapify(sticks)\n",
    "        while sticks:\n",
    "            item = heapq.heappop(sticks)\n",
    "            if sticks:\n",
    "                second = heapq.heappop(sticks)\n",
    "                result += item + second\n",
    "                heapq.heappush(sticks, item + second)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        n = len(sticks)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return sticks[0] + sticks[1]\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        heapq.heapify(sticks)\n",
    "        while len(sticks) > 1:\n",
    "            t1 = heapq.heappop(sticks)\n",
    "            t2 = heapq.heappop(sticks)\n",
    "\n",
    "            ans += (t1 + t2)\n",
    "\n",
    "            heapq.heappush(sticks, t1 + t2)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        def findmin()->int:\n",
    "            if not q:\n",
    "                return q2.popleft()\n",
    "            else:\n",
    "                if not q2:\n",
    "                    return q.popleft()\n",
    "                else:\n",
    "                    if q[0]<q2[0]: return q.popleft()\n",
    "                    else: return q2.popleft()\n",
    "        sticks.sort()\n",
    "        res = 0\n",
    "        q = deque(sticks)\n",
    "        q2 = deque()\n",
    "        while q or q2:\n",
    "            if len(q)+len(q2)==1: return res\n",
    "            first = findmin()\n",
    "            second = findmin()\n",
    "            first+=second\n",
    "            res+=first\n",
    "            q2.append(first)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        ans = 0\n",
    "        while sticks:\n",
    "            if len(sticks) == 1: \n",
    "                return ans\n",
    "            \n",
    "            tmp = heapq.heappop(sticks) + heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks, tmp)\n",
    "            ans += tmp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        ans = 0\n",
    "        while len(sticks) > 1:\n",
    "            l, r = heapq.heappop(sticks), heapq.heappop(sticks)\n",
    "            ans += l + r\n",
    "            heapq.heappush(sticks, l + r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_left\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        sticks = sorted(sticks)\n",
    "\n",
    "        ret = 0\n",
    "        dq = deque(sticks)\n",
    "\n",
    "        while len(dq) >= 2:\n",
    "            sum_ = dq.popleft() + dq.popleft()\n",
    "            insort_left(dq, sum_)\n",
    "            ret += sum_\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        ans=0\n",
    "        for i in range(len(sticks)-1):\n",
    "            a=heapq.heappop(sticks)\n",
    "            b=heapq.heappop(sticks)\n",
    "            ans+=a+b\n",
    "            heapq.heappush(sticks,(a+b))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        if len(sticks) == 1:\n",
    "            return 0\n",
    "        sticks.sort()\n",
    "        res = 0\n",
    "        while len(sticks) > 1:\n",
    "            sticks[0] = sticks[0] + sticks[1]\n",
    "            res += sticks[0]\n",
    "            sticks.pop(1)\n",
    "            sticks.sort()\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heapq.heapify(sticks)\n",
    "        res = []\n",
    "        while len(sticks) > 1:\n",
    "            num1 = heapq.heappop(sticks)\n",
    "            num2 = heapq.heappop(sticks)\n",
    "            heapq.heappush(sticks, num1+num2)\n",
    "            res.append(num1+num2)\n",
    "            # print(sticks, res)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_left\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        sticks = sorted(sticks)\n",
    "\n",
    "        ret = 0\n",
    "        while len(sticks) >= 2:\n",
    "            sum_ = sticks.pop(0) + sticks.pop(0)\n",
    "            insort_left(sticks, sum_)\n",
    "            ret += sum_\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_left\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        sticks = sorted(sticks)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "\n",
    "        while len(sticks) >= 2:\n",
    "            sum_ = sum(sticks[:2])\n",
    "            sticks = sticks[2:]\n",
    "            insort_left(sticks, sum_)\n",
    "            ret += sum_\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        heap = list()\n",
    "        cost = 0\n",
    "        for stick in sticks:\n",
    "            heappush(heap, stick)\n",
    "        if not heap:\n",
    "            return 0\n",
    "        while len(heap) > 1:\n",
    "            num1 = heappop(heap)\n",
    "            num2 = heappop(heap)\n",
    "            cost += num1 + num2\n",
    "            heappush(heap, num1 + num2)\n",
    "        return cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        for stick in sticks:\n",
    "            pq.put(stick)\n",
    "        res = 0\n",
    "        while pq.qsize() >= 2:\n",
    "            s1, s2 = pq.get(), pq.get()\n",
    "            sum = s1 + s2\n",
    "            res += sum\n",
    "            pq.put(sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connectSticks(self, sticks: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for l in sticks:\n",
    "            heappush(stack,l)\n",
    "\n",
    "        ans=0\n",
    "        while len(stack)>1:\n",
    "            l=heappop(stack)\n",
    "            l+=heappop(stack)\n",
    "            ans+=l\n",
    "            heappush(stack,l)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
